Since the early stages of the development of digital communication networks, the need for protocols that are fault tolerant and resistant to attack has been recognized. Fault tolerance implies, inter alia, the ability of certain network nodes to continue to use digital communication networks even if certain other nodes or links become disabled. Fault tolerance is provided by various networking protocols that will re-route messages around disabled nodes and links.
However, even nodes that are reachable and communicating may be compromised by a sophisticated cyber-attack. An attacker can also insert an unauthorized node into a digital communication network. In either case the node controlled by the attacker can undermine communications on the digital communication network.
One class of applications of digital communication networks essentially shares a set of values among a group of nodes in a network such that each node will obtain values from each other node. An object is for each node to acquire the same accurate set of values from other nodes in the group. Some nodes may be Byzantine faulty, i.e. one or more nodes may behave in an unpredictable, malicious manner, so that the nodes may announce conflicting, falsified values or may alter the contents of messages that pass through them. There are no restrictions on the type of behavior that these Byzantine faulty nodes may exhibit. Algorithms for solving this type of problem are called Byzantine Algorithms. Note that it is impossible to directly test a node for Byzantine faults because Byzantine nodes can respond to tests as normal nodes but then revert to Byzantine behavior after the test is over. Examples of applications of Byzantine Algorithms include Intrusion Detection and Countermeasure Systems, where Byzantine Agreement is used to identify and isolate nodes that have been compromised by hacker or rogue attacks, Sensor Networks, where Byzantine Agreement is used to agree on a common set of measured values even when some processors have been compromised, and Home Networks, where Byzantine Agreement is used to agree on a unique home networking key even when some devices have been compromised.
In recent years, there has been increased focus on wireless networks such as ad-hoc networks. Ad-hoc networks can be used for a variety of applications including sensor networks, and home networks. Ad-hoc networks are set up by autonomous network nodes that detect each other and establish communication links and message routing. Ad-hoc wireless networks may use a peer-to-peer communication protocol, in which case messages are routed through a sequence of intermediate nodes in order to minimize transmit power requirements. Networks that use peer-to-peer rounting are known as mesh networks. Mesh networks are typically not hierarchical, although certain for applications a particular node may perform a unique (e.g., supervisory) function with the network. Ad-hoc wireless networks are vulnerable to cyber-attack because it not necessary to physically connect to a transmission line in order to join an ad-hoc network. By their nature, ad-hoc wireless networks are intended to allow nodes to become part of the network. Once a malicious node has successfully joined a wireless ad-hoc network, messages will be routed through it and it will be able to transmit messages freely to other nodes. Thus, the malicious node may be able to compromise operation of the network.
In ad-hoc wireless networks, one or more network nodes may be mobile. Mobility poses a particular problem for Byzantine Algorithms that rely on network nodes being static.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.